class TreeNode:
    """
    二叉树定义
    """

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class StackSolution:
    """
    栈迭代遍历
    """

    def __init__(self):
        self.result = []

    def preorder(self, root: TreeNode):
        """
        前序遍历: root -> left -> right
        入栈顺序: right - > left -> root
        :param root:
        :return:
        """
        WHITE, GRAY = 0, 1
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((WHITE, node.left))
                stack.append((GRAY, node.val))
            else:
                self.result.append(node)
        return self.result

    def inorder(self, root: TreeNode):
        """
        中序遍历: left -> root -> right
        入栈顺序: right - > root -> left
        :param root:
        :return:
        """
        WHITE, GRAY = 0, 1
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((GRAY, node.val))
                stack.append((WHITE, node.left))
            else:
                self.result.append(node)
        return self.result


class Solution:
    """
    递归遍历
    """

    def __init__(self):
        self.path = []

    def preorder(self, root: TreeNode):
        if root:
            self.path.append(root.val)
            self.preorder(root.left)
            self.preorder(root.right)
        return self.path

    def inorder(self, root: TreeNode):
        if root:
            self.inorder(root.left)
            self.path.append(root.val)
            self.inorder(root.right)
        return self.path

    def postorder(self, root: TreeNode):
        if root:
            self.postorder(root.left)
            self.postorder(root.right)
            self.path.append(root.val)
        return self.path
